COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.s PATTERN DIRECTED COMPUTING
C00006 00003	.if false then begin
C00007 ENDMK
C⊗;
.s PATTERN DIRECTED COMPUTING

	
	Many useful algorithms are conveniently expressed by collections
of rules describing the transformation of expressions matching various
patterns into "corresponding" output patterns.
The following collection of rules for algebraic simplification is a
simple example:

.begin nofill
.n←12

	∂(n)$$(PLUS X 0) → X$

	∂(n)$$(PLUS 0 X) → X$

	∂(n)$$(TIMES X 1) → X$
!eqna1
	∂(n)$$(TIMES 1 X) → X$

	∂(n)$$(TIMES X 0) → 0$

	∂(n)$$(TIMES 0 X) → 0$
.end

We may consider programs that apply the set of rules once to an expression
or alternatively a program that applies the rules to an expression and its
subexpressions until they can no longer make any changes.

	A single application of ({eqn a1}) to $$(PLUS (TIMES A 1) 0)$
gives $$(TIMES A 1)$, while repeated application of the rule gives
$$A$.  Such simple rules have limited power (for example, they can't
easily be extended to handle sums and products of arbitrary numbers
of terms), but we will first consider how to implement them and then
consider extensions and improvements.

	A basic function is a simple pattern matcher ⊗inst defined by

.begin nofill group turnon "∂"
.n←12; m←16

∂(n)⊗⊗inst[pat, expr, a] ← ⊗
∂(n)⊗⊗    qif a = $$NO$ qthen $$NO$⊗
∂(n)⊗⊗    qelse qif isvar pat qthen ⊗
∂(n)⊗⊗        {assoc[pat, a]}[λz: ⊗
∂(n)⊗⊗            qif qn z qthen [pat . expr] . a⊗
!fcninst ∂(n)⊗⊗            qelse qif qd z = expr qthen a⊗
∂(n)⊗⊗            qelse $$NO$]⊗
∂(n)⊗⊗    qelse qif qat pat qthen [qif pat = expr qthen a qelse $$NO$]⊗
∂(n)⊗⊗    qelse qif qat expr qthen $$NO$⊗
∂(n)⊗⊗    qelse inst[qd pat, qd expr, inst[qa pat, qa expr, a]]⊗
.end

	⊗⊗inst[pat, expr, a]⊗ gives the result of matching the
pattern ⊗pat to the expression ⊗expr with some of the variables in
⊗pat already committed according to the a-list ⊗a.  If a match
is not possible, the value is the atom $$NO$.  Otherwise it is
an a-list giving the substitutions that convert ⊗pat into ⊗expr.  In
most applications the argument ⊗a has the value qNIL but is used
in the recursion.  We have

	⊗⊗inst[$$(PLUS X 0)$, $$(PLUS (TIMES A B) 0)$,qnil)] 
= $$(X.(TIMES A B))$⊗,

	⊗⊗inst[$$(PLUS X X)$, $$(PLUS (TIMES A B) 0)$,qnil)] = $$NO$⊗,

and

	⊗⊗inst[$$(PLUS X 0)$, $$(PLUS (TIMES A B) C)$,qnil)] = $$NO$⊗.


.if false then begin

	Include in progs a pattern matcher that setqs to variables.

.begin nofill select 2
.n←20
.group

∂(n)	setmatch[pat,exp] ← α{inst(pat,exp,nilα}
∂(n+4)	[λw.qif qn w qthen ⊗NIL 
∂(n+4)	qelse qprog[[z]
∂(n+8)	z ← w;
∂(n+4)l:∂(n+8)qif qn z qthen qreturn qnil;
∂(n+8)val[qaa z] ← qda z;
∂(n+8)	z ← qd z;
∂(n+8)	qgo loop]].
.end